package test.leecode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.stream.Collectors;


/**
 * 两数之和
 */
public class L01TwoSum {

    public static int[] twoSum(int[] nums, int target) {
        return mapCacheTwoSum(nums, target);
    }

    public static int[] mapCacheTwoSum1(int[] nums, int target) {
        Map<Integer,List<Integer>> numsMap = new HashMap<>();
        int[] result = null;
        for (int i = 0; i < nums.length; i++) {
            int b = nums[i];
            int c = target-b;
            if(numsMap.containsKey(c)) {
                final Integer if1 = i;
                List<Integer> idxList = numsMap.get(c)
                        .stream().filter(e->e<if1).collect(Collectors.toList());
                if(!idxList.isEmpty()) {
                    result = new int[]{idxList.get(0),i};
                }
            }else {
                numsMap.put(b,new ArrayList<>(Collections.singleton(i))); 
            }
        }
        return result;
    }

    /**
     * 使用Map缓存nums数组，key是nums的元素，value是List保存数组下标,因为nums的元素有重复的
     * 
     * Your runtime beats 45.9 % of java submissions
     * Your memory usage beats 5.01 % of java submissions (42.4 MB)
     * @param nums
     * @param target
     * @return
     */
    public static int[] mapCacheTwoSum(int[] nums, int target) {
        //Key v,Value [idx] 保存num和idx的映射，List是nums有重复的value
        Map<Integer,List<Integer>> numsMap = new HashMap<>();
        int[] result = null;
        for (int i = 0; i < nums.length; i++) {
            int b = nums[i];
            if(numsMap.containsKey(b)) {
                numsMap.get(b).add(i);
            }else{
                numsMap.put(b,new ArrayList<>(Collections.singleton(i)));
            }
            int c = target-b;
            if(numsMap.containsKey(c)) {
                final Integer if1 = i;
                List<Integer> idxList = numsMap.get(c)
                        .stream()
                        .filter(e->e<if1).collect(Collectors.toList());
                if(!idxList.isEmpty()) {
                    result = new int[]{idxList.get(0),i};
                }
            }
        }
        return result;
    }

    /**
     * 暴力循环
     * Your runtime beats 5.41 % of java submissions
     * Your memory usage beats 62.3 % of java submissions (41.4 MB)
     * @param nums
     * @param target
     * @return
     */
    public static int[] violenceLoop(int[] nums, int target) {
        for (int i = 0; i < nums.length; i++) {
            int a = nums[i];
            for (int n = 0; n < nums.length; n++) {
                if(i==n) continue;
                int b = nums[n];
                if (a + b == target) {
                    return new int[] { i, n };
                }
            }
        }
        return null;
    }

    public static void main(String[] args) {
        System.out.println(
                Arrays.toString(
                        L01TwoSum.twoSum(new int[] { 2, 7, 11, 15 }, 9)));
    }
}
